# 归并排序，
# 时间复杂度：O(N*logN)，log以2为底
# 空间复杂度：O(N)


def merge_sort(nums: list):
    """
    merge sort algorithm
    :param nums:  list of numbers
    :return: None
    """
    start = 0
    step = 2
    length = len(nums)
    # 将 nums 进行分组，分别按照2、4、8...个元素分组
    while int(step / 2) <= length:
        # print("step:", step)
        for group in range(start, length, step):
            # 归并排序的两个指针
            left_index = group
            right_index = group + int(step / 2)
            # 两个指针的最大值
            left_index_max = right_index
            right_index_max = group + step
            # 右边的指针可能存在越界的情况
            if right_index_max > length:
                right_index_max = length
            # 归并排序，临时存放的数组
            temp_nums = []
            while left_index < left_index_max and right_index < right_index_max and right_index < length:
                # 开始进行归并排序
                if nums[left_index] > nums[right_index]:
                    temp_nums.append(nums[right_index])
                    right_index += 1
                else:
                    temp_nums.append(nums[left_index])
                    left_index += 1
                # 当left_index先走到队尾，追加right_index的所有元素
                if left_index == left_index_max:
                    while right_index < right_index_max:
                        temp_nums.append(nums[right_index])
                        right_index += 1
                # 当right_index先走到队尾，追加left_index的所有元素
                if right_index == length or right_index == right_index_max:
                    while left_index < left_index_max:
                        temp_nums.append(nums[left_index])
                        left_index += 1
            # 将临时数组赋值到原数组
            for temp_index in range(len(temp_nums)):
                nums[group + temp_index] = temp_nums[temp_index]
        # 输出一下本轮归并的结果
        # print(nums)
        # 进行下一轮归并排序
        step *= 2


random_nums = [3, 5, 54, 42, 1, 3]
print("origin:", random_nums)
merge_sort(random_nums)
print("after:", random_nums)
